(1) Field of the Invention
The present invention relates to a packet forwarding device and a device for flow classifying for connecting a plurality of networks, further in details to a device for flow classifying and a packet forwarding device utilizing Content Addressable Memory (CAM).
(2) Description of the Related Art
According to a packet forwarding device, for example, a router for constituting Internet Protocol (IP) network, there is needed a flow classify function for classifying a flow to which a packet belongs from header information of a received packet. Here, a flow signifies a series of packets specified by a combination of an identifier (port number) of an input port or an output port of a packet, an IP address included in a header of a received packet, a protocol identifier, a Type of Service (TOS), and a priority and the like. The packet forwarding device carries out a flow control of determination of necessity or unnecessity of packet drop (filtering determination), determination of a packet forwarding priority (QoS: Quality of Service) for ensuring communication quality and the like for respective flow classified by a flow classifying portion.
In recent years, in order to deal with a rapid increase in IP traffic, there is investigated high speed formation of flow classifying. For example, there is disclosed “A flow identification method using content addressable memory” (Related Art 1) utilizing Content Addressable Memory (CAM) in Proceedings of Plenary Cession of the Society of Electronics, Information and Communication Engineers, 2000, SB-4-2.
In the case of flow classifying using CAM, as shown in FIG. 2, a search key KEY is generated by a flow controller 61 and is given to CAM 62. As shown in FIG. 3, CAM 62 is stored with a plurality of flow entries 620-1 through 620-n each describing an item value constituting a flow condition and an address of the flow entry having the flow condition in coincidence with the search key KEY is outputted. The flow controller 61 is provided with a context table 63 instructing a forwarding control to be executed to an input packet corresponding to the flow entry address of CAM 62, forwarding control instruction corresponding to an output address of the CAM, is read from the context table 63 and the input packet is processed in accordance with the instruction. According to CAM, a classifying time period of entry does not depend on a number of registered flow entries and therefore, the flow classifying can be constituted by high speed formation by utilizing CAM.
According to the related art 1, when all the items (field) necessary for flow classifying, for example, a source IP address 601, a destination IP address 602 and a protocol 603 are extracted as search key information from header information of the input packet and there are present a plurality of flow entries in coincidence with the search key in CAM 62, it is proposed to give a priority to the entry having the youngest address. Further, according to the related art 1, it is proposed to register the entry for flow classifying having a long bit width and the entry for forwarding control having a short bit width in one CAM and search simultaneously the flow identifying entry in coincidence with the flow classifying condition indicated by a search key and the entry for forwarding control in coincidence with a higher specific item of the flow identifying condition.
According to the IP network, in order to correspond to novel technologies of expansion of IP address by Ipv6 (RFC2460, Internet Protocol Version 6(Ipv6) Specification, R. Hinden et al), MPLS label stack (RFC3032, “MPLS Label Stack Encoding” E. Rosen et al) by MPLS Fast Reroute (draft-haskin-mpls-fast-reroute-05. text,“Method for Setting an Alternative Label Switched Paths to Handle Fast Reroute” D. Haskin et al), there is a tendency of expanding a bit length of a search key (for flow condition) at a flow classifying portion of a packet forwarding device and constituting a variety of flow conditions.
As a countermeasure against a case in which the bit length of the flow condition is increased and exceeds a search bit width capable of being provided by CAM, for example, in Proceeding of Plenary Cession of the Society of Electronics, Information and Communication Engineers, 2000, B-6-21, there is proposed “A flow identification method for Ipv6 using context addressable memory” for finding an entry in coincidence with the flow classifying condition by dividing the search key in two and executing twice search of flow entry search by the first half key and front entry search of the latter key.
According to the related art 2, as shown in FIG. 4, CAM is divided into a flow entry region 62A for the first half and a flow entry region 62B for the latter half and a class field 621 and a rule number field 622 of the first and the latter halves are given to the respective flow entries. Further, in search result holding tables 63 (63A, 63B), there are designated necessity for the later search 631, a rule number 632 and action 633. According to the first half key KEY-A and the flow entry of the first half, the rule number field 622 becomes Don't Care value, as a result of CAM search by the first half key KEY-A, the rule number is specified from the search result holding table 63A and by CAM search by the latter half key KEY-B applied with the rule number, an action to be executed to the input packet is determined.
Further, according to JP-A-2001-156840 (Related Art 3), there is proposed a flow classifying device in which there are extracted specific fields capable of constituting a flow condition, for example, a source address, a destination address, a protocol, and Type of Service (TOS) included in an IP header, and a source port and a destination port included in TCP or UDP header, a flag bit for masking previously registered in a search flag table corresponding to an input logical link number, is applied to these field items, thereby, for the respective input logical link, effective data is left only to an item (field) necessary for flow classification, there is generated a search key in the form in which an item which is not needed for flow classification is substituted for an ineffective value and access is made to CAM for a flow search table by the search key.
However, the above-described Related Art 2 proposes one resolution measure when the bit length of the search key is increased and does not intend to shorten the bit lengths of the search key and the flow entry. Further, according to the related art 3, by adopting general purpose search key format including all the items of header information which can constitute the flow identifying condition and masking an item of header information which is not needed of the respective input logical link, checking of the search key and flow entry is facilitated, similar to the related art 2, it is not intended to shorten the bit lengths of the search key and the flow entry.
When a variety of the flow classifying conditions are dealt with by the search key of the same format for general purpose in this way, the bit length of the search key is increased to face the problem of pin neck and deficiency in capacity of CAM in CAM 62 and LSI 61 for flow control.